package permutation;

public class Main {

	public static void main(String[] args) {
		//直接运行模板代码
		dfs(0,3);
		//初始化辅助变量
		b = new int[20];
		vis = new boolean[20];
		//运行案例代码
		dfs_names(0,3);
		
	}
	
	//20个下标待排列
	static int[] a = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
	//保存每次全排列的结果
	static int[] b = new int[20];
	//记录每个位置的下标是否用过
	static boolean[] vis = new boolean[20];
	//dfs从小到大输出排列
	//s:排列开始位置
	//t:排列结束位置
	static void dfs(int s,int t){
		if(s==t) {
			//找到一个全排列情况
			for(int i=0;i<t;i++) {
				System.out.print(b[i]);
			}
			System.out.println();
			return;
		}
		for(int i=0;i<t;i++) {
			//找未使用的下标，设为使用，然后开始dfs
			if(!vis[i]) {
				vis[i] = true;
				b[s] = a[i];
				dfs(s+1,t);
				//回溯，退回时vis[i]复原
				vis[i] = false;
			}
		}
	}
	
	//例：names的全部组合情况
	//为方便套用模板代码，names的0下标元素留空，实际从1下标开始排列
	static String[] names = {"","Tom","Mike","Lucy"};
	//模板稍作修改
	static void dfs_names(int s,int t){
		if(s==t) {
			//找到一个全排列情况
			System.out.print("[");
			for(int i=0;i<t;i++) {
				System.out.print(names[b[i]] + " ");
			}
			System.out.println("]");
			return;
		}
		for(int i=0;i<t;i++) {
			//找未使用的下标，设为使用，然后开始dfs
			if(!vis[i]) {
				vis[i] = true;
				b[s] = a[i];
				dfs_names(s+1,t);
				//回溯，退回时vis[i]复原
				vis[i] = false;
			}
		}
	}
}
